package com.da.javatest.leetCode;

import java.util.Arrays;

/**
 * @author chenlida
 * @date 2018/12/11 14:23
 * @description
 */
public class Code654 {
    //public static void main(String[] args) {
    //    new Code654().constructMaximumBinaryTree(new int[] {3, 2, 1, 6, 0, 5});
    //}
    //
    //public TreeNode constructMaximumBinaryTree(int[] nums) {
    //    int size = nums.length / 2;
    //    int[] nums1 = new int[size];
    //    int[] nums2 = new int[size];
    //    System.arraycopy(nums, 0, nums1, 0, size);
    //    System.arraycopy(nums, size, nums2, 0, size);
    //    Arrays.sort(nums1);
    //    Arrays.sort(nums2);
    //    int max = nums1[nums1.length - 1] > nums2[nums2.length - 1] ? nums1[nums1.length - 1] : nums2[nums2.length
    // - 1];
    //    TreeNode treeNode = new TreeNode(max);
    //    fillTreeNode(treeNode, true, nums1);
    //    fillTreeNode(treeNode, false, nums2);
    //    return treeNode;
    //}
    //
    //private void fillTreeNode(TreeNode treeNode, boolean left, int[] nums) {
    //    if (left) {
    //        for (int i = nums.length - 1; i >= 0; i--) {
    //            if (treeNode.val == nums[i]) {
    //                continue;
    //            }
    //            getNullTreeNode(treeNode, left).left = new TreeNode(nums[i]);
    //        }
    //    } else {
    //        for (int i = nums.length - 1; i >= 0; i--) {
    //            if (treeNode.val == nums[i]) {
    //                continue;
    //            }
    //            getNullTreeNode(treeNode, left).right = new TreeNode(nums[i]);
    //        }
    //    }
    //}
    //
    //private TreeNode getNullTreeNode(TreeNode treeNode, boolean left) {
    //    if (left) {
    //        if (treeNode.left != null) {
    //            return getNullTreeNode(treeNode.left, left);
    //        }
    //        return treeNode;
    //    } else {
    //        if (treeNode.right != null) {
    //            return getNullTreeNode(treeNode.right, left);
    //        }
    //        return treeNode;
    //    }
    //}

    public static void main(String[] args) {
        new Code654().constructMaximumBinaryTree(new int[] {3, 2, 1, 6, 0, 5});
    }

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return buildTree(nums, 0, nums.length - 1);
    }

    public TreeNode buildTree(int[] nums, int start, int end) {
        if (start > end) {
            return null;
        }
        int maxIndex = maxIndex(nums, start, end);
        TreeNode root = new TreeNode(nums[maxIndex]);
        root.left = buildTree(nums, start, maxIndex - 1);
        root.right = buildTree(nums, maxIndex + 1, end);
        return root;
    }

    public int maxIndex(int[] arr, int start, int end) {

        int maxIndex = start;
        for (int i = start; i <= end; i++) {
            if (arr[i] > arr[maxIndex]) {
                maxIndex = i;
            }
        }
        return maxIndex;
    }
}